package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/restore-the-array/
 * @create 2025/9/5 22:55
 * @since JDK17
 */

public class Solution84 {
    int N = ((int) (1e9 + 7));

    int len(int num) {
        int ans = 0;
        while (num != 0) {
            num /= 10;
            ans++;
        }
        return ans;
    }


    public int numberOfArrays(String s, int k) {
        int n = s.length(), m = len(k);
        long[] dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            long num = 0, base = 1;
            for (int j = i - 1; j < i + m; j++, base *= 10) {
                if (s.charAt(j) == '0') {
                    continue;
                }
                num += base * (s.charAt(j) - '0');
                if (num <= k) {
                    dp[i] = (dp[i] + dp[j]) % N;
                }
            }
        }

        return ((int) dp[n]);
    }
}
